package primary.primary0;

import java.util.PriorityQueue;

/**
 * 链表合并, 边界条件, 分治, 优先队列,
 * 多个合并，就像是分治的条件
 */
public class S0023合并K个升序链表 {

    /**
     * 确实分治会清晰一点
     * 方法合并一段区间之内的链表
     * 如果区间左=右，那么返回自己
     * 如果左 != 右，那么切割成两部分调用自己，再把两部分合并起来
     */


    /**
     * 优先队列，厉害的
     * 队列数量为lists.length，然后每个list首节点放进去，然后把队列第一个拿出来，它是个节点，它肯定是最小的了，
     * 第二步:把它的下一个节点放到队列里，
     * 第三步:再取队列首节点，
     * 循环2 3步，这样就实现了一个个取最小值，复杂度是  所有节点数量*logk，不错
     */



    /**
     * 32, 如果是分治的话, 复杂度就会nlogn, 如果是单纯每个都往上一个上面加, 那就是n^2
     * 注意这是个ListNode[], 然后里面每一个元素都是链表的头结点
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int totalLen = lists.length;
        if(totalLen <= 1){
            return totalLen == 0? null: lists[0];
        }
        mergeTwoLists(lists, 0, totalLen / 2 - 1, totalLen / 2, totalLen - 1);
        return lists[0];
    }
    /*因为修改的都是引用变量, 所以也不用传递什么东西回去, 该不该把lists改成全局?*/
    public void mergeTwoLists(ListNode[] lists, int leftStart, int leftEnd, int rightStart, int rightEnd){
        if(leftStart != leftEnd){
            // 左边是一个未被合并的list
            mergeTwoLists(lists, leftStart, (leftStart + leftStart)/2, (leftStart + leftStart)/2 + 1, leftEnd);
        }
        if(rightStart != rightEnd){
            mergeTwoLists(lists, rightStart, (rightStart + rightStart)/2, (rightStart + rightStart)/2 + 1, rightEnd);
        }
        // 处理结束, 可以把rightStart位置上的list移到leftStart上了
        // 如果leftStart == leftEnd, 那么表示左边就不用动的, 右同
        if(lists[leftStart] == null){
            lists[leftStart] = lists[rightStart];
            return;
        }
        if(lists[rightStart] == null){
            return;
        }
        // 这个合并两个链表的方式, 不太优雅。
        ListNode leftPre = new ListNode(-1, lists[leftStart]);
        ListNode leftInit = leftPre; // 记录一下虚拟头
        ListNode leftPosi = lists[leftStart];
        ListNode rightPosi = lists[rightStart];
        ListNode rightAft = rightPosi.next;
        while(leftPosi != null && rightPosi != null){
            if(leftPosi.val >= rightPosi.val){
                // 把right的当前节点插到left的当前节点之前, 因为left前面补了一个-1, 所以总能通过位移到达这么个位置
                leftPre.next = rightPosi;
                rightPosi.next = leftPosi;
                leftPre = leftPre.next;
                rightPosi = rightAft;
                rightAft = rightPosi == null? null: rightPosi.next;
            }else{
                leftPosi = leftPosi.next;
                leftPre = leftPre.next;
            }
        }
        if(leftPosi == null){
            leftPre.next = rightPosi;
        }
        lists[leftStart] = leftInit.next;
    }

    /**
     * 别人的方法, 这种传参方式要优雅一点
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge2(lists, 0, lists.length - 1);
    }

    public ListNode merge2(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists2(merge2(lists, l, mid), merge2(lists, mid + 1, r));
    }


    /**
     * 这个merge就比较优雅了, 造一个虚拟头, 然后把a, b的头逐个往上面塞, 没那么多边界值需要考虑
     * 我是想把b往a里塞, 其实是一样的, 先把两个链表往虚拟头里塞, 然后把虚拟头塞给a, 不就行了。
     */
    public ListNode mergeTwoLists2(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }


    /**
     * 别人的方法, 学学这个自定义Comparator
     * 就把他们都放到一个自定义的优先队列里, 然后逐个拿出来再放回去,
     * 每次拿出来再放回去会往结果链表上加一个值
     */
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists3(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }


}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
